Publication Details
Andrey Chernikov and Nikos Chrisochoides.
Published in SIAM Journal on Scientific Computing, Volume 34, No. 3, pages A1333 -- A1350, 2012
Abstract
Mesh generation by Delaunay refinement is a widely used technique for constructing guaranteed quality triangular and tetrahedral meshes. The quality guarantees are usually provided in terms of the bounds on circumradius-to-shortest edge ratio and on the grading of the resulting mesh. Traditionally circumcenters of skinny elements and middle points of boundary faces and edges are used for the positions of inserted points. However, recently variations of the traditional algorithms are being proposed that are designed to achieve certain optimization objectives by inserting new points in neighborhoods of the center points. In this paper we propose a general approach to the selection of point positions by defining one-, two-, and three-dimensional selection regions such that any point insertion strategy based on these regions is automatically endowed with the theoretical guarantees proven here. In particular, for the input models defined by planar linear complexes under the assumption that no input angle is less than 90 degrees, we prove the termination of the proposed generalized algorithm, as well as fidelity and good grading of the resulting meshes.
